home *** CD-ROM | disk | FTP | other *** search
/ Scene Storm / Scene Storm - Volume 1.iso / coding / c / lha_axeman / slide.c < prev    next >
C/C++ Source or Header  |  1995-09-01  |  9KB  |  391 lines
  1. /***********************************************************
  2.     slide.c -- sliding dictionary with percolating update
  3. ***********************************************************/
  4. #include "lharc.h"
  5. #include "slidehuf.h"
  6. #include "intrface.h"
  7.  
  8. #define PERCOLATE  1
  9. #define NIL        0
  10.  
  11. node *next = NULL;
  12. int unpackable;
  13. unsigned long origsize, compsize;
  14. unsigned short dicbit;
  15. unsigned short maxmatch;
  16. unsigned long count;
  17. unsigned short loc;
  18. unsigned char *text;
  19. int prev_char;
  20.  
  21. static unsigned long encoded_origsize;
  22.  
  23. static struct encode_option encode_define[2] = {
  24. #if defined(__STDC__) || defined(AIX)
  25. /* lh1 */
  26.     {(void(*)())output_dyn,
  27.      (void(*)())encode_start_fix,
  28.      (void(*)())encode_end_dyn},
  29. /* lh4, 5 */
  30.     {(void(*)())output_st1,
  31.     (void(*)())encode_start_st1,
  32.     (void(*)())encode_end_st1}
  33. #else
  34. /* lh1 */
  35.     {(int(*)())output_dyn,
  36.      (int(*)())encode_start_fix,
  37.      (int(*)())encode_end_dyn},
  38. /* lh4, 5 */
  39.     {(int(*)())output_st1,
  40.     (int(*)())encode_start_st1,
  41.     (int(*)())encode_end_st1}
  42. #endif
  43. };
  44.  
  45. static struct decode_option decode_define[7] =
  46. {
  47.   /* lh1 */
  48.     {decode_c_dyn, decode_p_st0, decode_start_fix},
  49.   /* lh2 */
  50.     {decode_c_dyn, decode_p_dyn, decode_start_dyn},
  51.   /* lh3 */
  52.     {decode_c_st0, decode_p_st0, decode_start_st0},
  53.   /* lh4 */
  54.     {decode_c_st1, decode_p_st1, decode_start_st1},
  55.   /* lh5 */
  56.     {decode_c_st1, decode_p_st1, decode_start_st1},
  57.   /* lzs */
  58.     {decode_c_lzs, decode_p_lzs, decode_start_lzs},
  59.   /* lz5 */
  60.     {decode_c_lz5, decode_p_lz5, decode_start_lz5}
  61. };
  62.  
  63. static struct encode_option encode_set;
  64. static struct decode_option decode_set;
  65.  
  66. static node pos, matchpos, avail,
  67.         *position, *parent, *prev;
  68. static int remainder, matchlen;
  69. static unsigned char *level, *childcount;
  70. static unsigned short dicsiz;
  71. static unsigned short max_hash_val;
  72. static unsigned short hash1, hash2;
  73.  
  74. int encode_alloc(method)
  75. int method;
  76. {
  77.   if (method == 1) {
  78.     encode_set = encode_define[0];
  79.     maxmatch = 60;
  80.     dicbit = 12;
  81.   } else {
  82.     encode_set = encode_define[1];
  83.     maxmatch = MAXMATCH;
  84.     dicbit = 13;
  85.   }
  86.   while (1) {
  87.     dicsiz = 1 << dicbit;
  88.     max_hash_val = 3 * dicsiz + (dicsiz / 512 + 1) * UCHAR_MAX;
  89.     text = (unsigned char *)malloc(dicsiz * 2 + maxmatch);
  90.     level = (unsigned char *)malloc((dicsiz + UCHAR_MAX + 1) * sizeof(*level));
  91.     childcount = (unsigned char *)malloc((dicsiz + UCHAR_MAX + 1) * sizeof(*childcount));
  92. #if PERCOLATE
  93.     position = (node *)malloc((dicsiz + UCHAR_MAX + 1) * sizeof(*position));
  94. #else
  95.     position = (node *)malloc(dicsiz * sizeof(*position));
  96. #endif
  97.     parent     = (node *)malloc(dicsiz * 2 * sizeof(*parent));
  98.     prev       = (node *)malloc(dicsiz * 2 * sizeof(*prev));
  99.     next       = (node *)malloc((max_hash_val + 1) * sizeof(*next));
  100.     if (next == NULL || 
  101.     method > 1 && alloc_buf() == NULL) {
  102.       if (next) free(next);
  103.       if (prev) free(prev);
  104.       if (parent) free(parent);
  105.       if (position) free(position);
  106.       if (childcount) free(childcount);
  107.       if (level) free(level);
  108.       if (text) free(text);
  109.     } else {
  110.       break;
  111.     }
  112.     if (--dicbit < 12 )
  113.       /* error(MEMOVRERR, NULL); */
  114.       exit( 207 );
  115.   }
  116.   if (method == 5)
  117.     method = dicbit - 8;
  118.   return method;
  119. }
  120.  
  121. static void init_slide(void)
  122. {
  123.     node i;
  124.  
  125.     for (i = dicsiz; i <= dicsiz + UCHAR_MAX; i++) {
  126.         level[i] = 1;
  127. #if PERCOLATE
  128.             position[i] = NIL;  /* sentinel */
  129. #endif
  130.     }
  131.     for (i = dicsiz; i < dicsiz * 2; i++) parent[i] = NIL;
  132.     avail = 1;
  133.     for (i = 1; i < dicsiz - 1; i++) next[i] = i + 1;
  134.     next[dicsiz - 1] = NIL;
  135.     for (i = dicsiz * 2; i <= max_hash_val; i++) next[i] = NIL;
  136.     hash1 = dicbit - 9;
  137.     hash2 = dicsiz * 2;
  138. }
  139.  
  140. #define HASH(p, c) ((p) + ((c) << hash1) + hash2)
  141.  
  142. static /* inline */ node child(q, c)
  143.     /* q's child for character c (NIL if not found) */
  144. node q;
  145. unsigned char c;
  146. {
  147.     node r;
  148.  
  149.     r = next[HASH(q, c)];
  150.     parent[NIL] = q;  /* sentinel */
  151.     while (parent[r] != q) r = next[r];
  152.     return r;
  153. }
  154.  
  155. static /* inline */ void makechild(q, c, r)
  156.     /* Let r be q's child for character c. */
  157. node q;
  158. unsigned char c;
  159. node r;
  160. {
  161.     node h, t;
  162.  
  163.     h = HASH(q, c);
  164.     t = next[h];  next[h] = r;  next[r] = t;
  165.     prev[t] = r;  prev[r] = h;
  166.     parent[r] = q;  childcount[q]++;
  167. }
  168.  
  169. static /*inline*/ void split(old)
  170. node old;
  171. {
  172.     node new, t;
  173.  
  174.     new = avail;  avail = next[new];  childcount[new] = 0;
  175.     t = prev[old];  prev[new] = t;  next[t] = new;
  176.     t = next[old];  next[new] = t;  prev[t] = new;
  177.     parent[new] = parent[old];
  178.     level[new] = matchlen;
  179.     position[new] = pos;
  180.     makechild(new, text[matchpos + matchlen], old);
  181.     makechild(new, text[pos + matchlen], pos);
  182. }
  183.  
  184. static void insert_node(void)
  185. {
  186.     node q, r, j, t;
  187.     unsigned char c, *t1, *t2;
  188.  
  189.     if (matchlen >= 4) {
  190.         matchlen--;
  191.         r = (matchpos + 1) | dicsiz;
  192.         while ((q = parent[r]) == NIL) r = next[r];
  193.         while (level[q] >= matchlen) {
  194.             r = q;  q = parent[q];
  195.         }
  196. #if PERCOLATE
  197.             t = q;
  198.             while (position[t] < 0) {
  199.                 position[t] = pos;  t = parent[t];
  200.             }
  201.             if (t < dicsiz) position[t] = pos | SHRT_MIN;
  202. #else
  203.             t = q;
  204.             while (t < dicsiz) {
  205.                 position[t] = pos;  t = parent[t];
  206.             }
  207. #endif
  208.     } else {
  209.         q = text[pos] + dicsiz;  c = text[pos + 1];
  210.         if ((r = child(q, c)) == NIL) {
  211.             makechild(q, c, pos);  matchlen = 1;
  212.             return;
  213.         }
  214.         matchlen = 2;
  215.     }
  216.     for ( ; ; ) {
  217.         if (r >= dicsiz) {
  218.             j = maxmatch;  matchpos = r;
  219.         } else {
  220.             j = level[r];
  221.             matchpos = position[r] & SHRT_MAX;
  222.         }
  223.         if (matchpos >= pos) matchpos -= dicsiz;
  224.         t1 = &text[pos + matchlen];  t2 = &text[matchpos + matchlen];
  225.         while (matchlen < j) {
  226.             if (*t1 != *t2) {  split(r);  return;  }
  227.             matchlen++;  t1++;  t2++;
  228.         }
  229.         if (matchlen == maxmatch) break;
  230.         position[r] = pos;
  231.         q = r;
  232.         if ((r = child(q, *t1)) == NIL) {
  233.             makechild(q, *t1, pos);  return;
  234.         }
  235.         matchlen++;
  236.     }
  237.     t = prev[r];  prev[pos] = t;  next[t] = pos;
  238.     t = next[r];  next[pos] = t;  prev[t] = pos;
  239.     parent[pos] = q;  parent[r] = NIL;
  240.     next[r] = pos;  /* special use of next[] */
  241. }
  242.  
  243. static void delete_node(void)
  244. {
  245. #if PERCOLATE
  246.         node q, r, s, t, u;
  247. #else
  248.         node r, s, t, u;
  249. #endif
  250.  
  251.     if (parent[pos] == NIL) return;
  252.     r = prev[pos];  s = next[pos];
  253.     next[r] = s;  prev[s] = r;
  254.     r = parent[pos];  parent[pos] = NIL;
  255.     if (r >= dicsiz || --childcount[r] > 1) return;
  256. #if PERCOLATE
  257.         t = position[r] & SHRT_MAX;
  258. #else
  259.         t = position[r];
  260. #endif
  261.     if (t >= pos) t -= dicsiz;
  262. #if PERCOLATE
  263.         s = t;  q = parent[r];
  264.         while ((u = position[q]) < 0) {
  265.             u &= SHRT_MAX;  if (u >= pos) u -= dicsiz;
  266.             if (u > s) s = u;
  267.             position[q] = (s | dicsiz);  q = parent[q];
  268.         }
  269.         if (q < dicsiz) {
  270.             if (u >= pos) u -= dicsiz;
  271.             if (u > s) s = u;
  272.             position[q] = (s | dicsiz) | SHRT_MIN;
  273.         }
  274. #endif
  275.     s = child(r, text[t + level[r]]);
  276.     t = prev[s];  u = next[s];
  277.     next[t] = u;  prev[u] = t;
  278.     t = prev[r];  next[t] = s;  prev[s] = t;
  279.     t = next[r];  prev[t] = s;  next[s] = t;
  280.     parent[s] = parent[r];  parent[r] = NIL;
  281.     next[r] = avail;  avail = r;
  282. }
  283.  
  284. /* static */void get_next_match(void)
  285. {
  286.     int n;
  287.  
  288.     remainder--;
  289.     if (++pos == dicsiz * 2) {
  290.         bcopy(&text[dicsiz], &text[0], dicsiz + maxmatch);
  291.         n = fread_crc(&text[dicsiz + maxmatch], dicsiz, infile);
  292.         encoded_origsize += n;
  293.         remainder += n;  pos = dicsiz;
  294.     }
  295.     delete_node();  insert_node();
  296. }
  297.  
  298. void encode(interface)
  299. struct interfacing *interface;
  300. {
  301.     int lastmatchlen, dicsiz1;
  302.     node lastmatchpos;
  303.  
  304.     infile = interface -> infile;
  305.     outfile = interface -> outfile;
  306.     origsize = interface -> original;
  307.     compsize = count = 0L;
  308.     crc = unpackable = 0;
  309.     init_slide();  encode_set.encode_start();
  310.     dicsiz1 = dicsiz - 1;
  311.     pos = dicsiz + maxmatch;
  312.     memset(&text[pos], ' ', dicsiz);
  313.     remainder = fread_crc(&text[pos], dicsiz, infile);
  314.     encoded_origsize = remainder;
  315.     matchlen = 0;
  316.     insert_node();
  317.     while (remainder > 0 && ! unpackable) {
  318.         lastmatchlen = matchlen;  lastmatchpos = matchpos;
  319.         get_next_match();
  320.         if (matchlen > remainder) matchlen = remainder;
  321.         if (matchlen > lastmatchlen || lastmatchlen < THRESHOLD) {
  322.             encode_set.output(text[pos - 1], 0);
  323.             count++;
  324.         } else {
  325.             encode_set.output(lastmatchlen + (UCHAR_MAX + 1 - THRESHOLD),
  326.                    (pos - lastmatchpos - 2) & dicsiz1);
  327.             while (--lastmatchlen > 0) {
  328.                 get_next_match();
  329.                 count++;
  330.             }
  331.             if (matchlen > remainder) matchlen = remainder;
  332.         }
  333.     }
  334.     encode_set.encode_end();
  335.     interface -> packed = compsize;
  336.     interface -> original = encoded_origsize;
  337. }
  338.  
  339. void decode(interface)
  340. struct interfacing *interface;
  341. {
  342.     int i, j, k, c, dicsiz1, offset;
  343.  
  344.     infile = interface -> infile;
  345.     outfile = interface -> outfile;
  346.     dicbit = interface -> dicbit;
  347.     origsize = interface -> original;
  348.     compsize = interface -> packed;
  349.     decode_set = decode_define[interface -> method - 1];
  350.     crc = 0;
  351.     prev_char = -1;
  352.     dicsiz = 1 << dicbit;
  353.     text = (unsigned char *)malloc(dicsiz);
  354.     if (text == NULL)
  355.         /* error(MEMOVRERR, NULL); */
  356.         exit( errno );
  357.     memset(text, ' ', dicsiz);
  358.     decode_set.decode_start();
  359.     dicsiz1 = dicsiz - 1;
  360.     offset = (interface -> method == 6) ? 0x100 - 2 : 0x100 - 3;
  361.     count = 0;  loc = 0;
  362.     while (count < origsize) {
  363.         c = decode_set.decode_c();
  364.         if (c <= UCHAR_MAX) {
  365.             text[loc++] = c;
  366.             if (loc == dicsiz) {
  367.                 fwrite_crc(text, dicsiz, outfile);
  368.                 loc = 0;
  369.             }
  370.             count++;
  371.         } else {
  372.             j = c - offset;
  373.             i = (loc - decode_set.decode_p() - 1) & dicsiz1;
  374.             count += j;
  375.             for (k = 0; k < j; k++) {
  376.                 c = text[(i + k) & dicsiz1];
  377.                 text[loc++] = c;
  378.                 if (loc == dicsiz) {
  379.                     fwrite_crc(text, dicsiz, outfile);
  380.                     loc = 0;
  381.                 }
  382.             }
  383.         }
  384.     }
  385.     if (loc != 0) {
  386.         fwrite_crc(text, loc, outfile);
  387.     }
  388.     free(text);
  389. }
  390.  
  391.